// Implementation of a view that generates lists of views
// Copyright 2005 (C) Ralph Thomas

#include <view/generator.h>
#include <view/rectangle.h>
#include <binder.hpp>
#include <deque>
#include <vector>
#include <map>
#include <boost/signals.hpp>
#include <util/concepts/list.h>
#include <iostream>

//
/// There is an optimization that the generator makes where
/// it will reuse items that are no longer visible and try
/// to change them (via binder_t::substitute) into the item
/// it wants. This hasn't been well tested, and a binder
/// that doesn't go back to it's original state before doing
/// a substitute could break everything.
//
#define RISKY_SUBSTITUTE_OPT	false
//
/// The maximum number of real items that we keep in excess
/// of what we need. This number may end up becoming a multiplier
/// against the number of needed real items in the future.
//
#define MAX_EXCESS_REAL_ITEMS	0

namespace view { struct item_t; };
//
/// Is the point [x, y] inside the rectangle [rw x rh + rx + ry]?
//
inline bool pointin( long x, long y, long rx, long ry, long rw, long rh ) {
	if( x < rx ) return false;
	if( x > rx + rw ) return false;
	if( y < ry ) return false;
	if( y > ry + rh ) return false;
	return true;
}
//
/// See if a view::rectangle contains any part of an adobe::eve_t::place_data_t.
///
/// \param	rect	the rectangle to test.
/// \param	pdata	the place data to test.
///
/// \return	true if the rectangle contains some part of the place data, false
///		otherwise.
//
inline bool contains( const view::rectangle& rect, const adobe::eve_t::place_data_t& pdata ) {
	const long wx = pdata.horizontal().position_m;
	const long wy = pdata.vertical().position_m;
	const long ww = pdata.horizontal().length_m;
	const long wh = pdata.vertical().length_m;
	if( pointin( wx, wy, rect.x, rect.y, rect.w, rect.h ) )		return true;
	if( pointin( wx + ww, wy, rect.x, rect.y, rect.w, rect.h ) )	return true;
	if( pointin( wx + ww, wy + wh, rect.x, rect.y, rect.w, rect.h ) ) return true;
	if( pointin( wx, wy + wh, rect.x, rect.y, rect.w, rect.h ) )	return true;
	//
	// What if the pdata is larger than the rect.
	//
	if( (wx < rect.x) && (wx + ww > rect.x + rect.w) ) {
		if( (wy < rect.y) && (wy + wh > rect.y + rect.h) )	return true;
		if( (wy > rect.y) && (wy + wh < rect.y + rect.h) )	return true;
	}
	if( (wy < rect.y) && (wy + wh > rect.y + rect.h) ) {
		// We already caught the other case above.
		if( (wx > rect.x) && (wx + ww < rect.x + rect.w) )	return true;
	}
	return false;
}
namespace view {
std::ostream& operator<<( std::ostream& os, const adobe::eve_t::place_data_t& pdata ) {
	os << pdata.horizontal().length_m << "x" << pdata.vertical().length_m << "+" << pdata.horizontal().position_m << "+" << pdata.vertical().position_m;
	return os;
}
}
namespace view {
	//
	/// The record class is used to keep a record of all the views which
	/// the generator needs to create. It represents a single view.
	//
	class record {
	  public:
		typedef std::vector<record*>	childList;
		typedef std::vector<adobe::binder_ptr_t> binder_list_t;
		//
		/// The children of this view record.
		//
		childList			children;
		//
		/// The parameters for creating this view with.
		//
		adobe::dictionary_t		parameters;
		//
		/// The classname of this view.
		//
		adobe::name_t			name;
		//
		/// Create a new record, of the given parent, name,
		/// parameters. Maybe more is required to have
		/// generators inside generators (like factory) or
		/// scrollviews inside generators (like token).
		///
		/// \param	parent		the parent record.
		/// \param	n		the name of this view.
		/// \param	params		the parameters for this view.
		//
		record( boost::any parent, adobe::name_t n,
			const adobe::dictionary_t& params )
			: parameters( params ), name( n ) {
			//
			// If we are given a parent, then add ourselves to
			// it's list of children.
			//
			record* rec_parent = 0;
			if( parent.type() == typeid(record*) ) {
				rec_parent = boost::any_cast<record*>( parent );
			} else return;
			if( rec_parent ) rec_parent->children.push_back( this );
		}
		//
		/// Release this record and all of it's children.
		//
		~record() {
			childList::iterator first( children.begin() );
			childList::iterator last( children.end() );
			for( childList::iterator i = first; i != last; i++ ) delete *i;
		}
		//
		/// This function will build a root record. The root record is usually
		/// a row container, and can inform the generator of the size that Eve
		/// assigns to it (hence building it manually, rather than using the
		/// row_factory). This function can also build stub entries which can
		/// be replaced with real entries when required.
		//
		adobe::widget_node_t build_root( const adobe::factory_token_t& token,
			const adobe::widget_node_t& parent,
			const adobe::eve_t::signal_suite_t::eve_place_proc_t& placer,
		        long width = 0, long height = 0, bool is_stub = false ) {
			adobe::eve_t::calculate_data_t	cdata;
			adobe::eve_t::signal_suite_t	signals;

			cdata.placement_m = adobe::eve_t::place_row;
			cdata.horizontal().length_m	= width;
			cdata.vertical().length_m	= height;
			if( children.size() == 1 ) {
				//
				// If we only have one child then use it's calculate data.
				//
				adobe::setup_calculate_data(cdata, children[0]->parameters);
			}
			cdata.vertical().suppress_m	= false;
			cdata.create_m			= false;
			signals.eve_place_proc_m	= placer;
			
			adobe::eve_t::iterator eve_token = token.layout_m.add_view_element(
				parent.eve_token_m,
				adobe::eve_t::insert_element_t(
					cdata,
					!is_stub,
					parameters,
					signals)
				);

			return adobe::widget_node_t( parent.size_m, eve_token,
				parent.display_token_m, parent.overlay_token_m );
		}
		//
		/// This function will build all of the children of a record.
		///
		/// \param	token		the factory token to build with.
		/// \param	parent		the parent widget node to insert under.
		/// \param	f		the factory function to build with.
		/// \param	sub_name	the name to substitute in.
		/// \param	sub_value	the value to substitute in.
		//
		void build_children( const adobe::factory_token_t& token,
			const adobe::widget_node_t& parent, factory& f, const adobe::name_t&
			sub_name, const adobe::value_t& sub_value, binder_list_t& binder_list ) {
			//
			// Iterate through all children and build them.
			//
			childList::iterator first( children.begin() );
			childList::iterator last( children.end() );
			for( childList::iterator i = first; i != last; i++ ) {
				if( !*i ) continue;
				(*i)->build( token, parent, f, sub_name, sub_value, binder_list );
			}
		}
		//
		/// This function will build the record and it's children, returning
		/// a widget node.
		///
		/// \param	token		the factory token to build with.
		/// \param	parent		the parent widget node to insert under.
		/// \param	f		the factory function to build with.
		/// \param	sub_name	the name to substitute in.
		/// \param	sub_value	the value to substitute in.
		///
		/// \return	the widget node created from this record.
		//
		adobe::widget_node_t build( const adobe::factory_token_t& token,
			const adobe::widget_node_t& parent, factory& f, const adobe::name_t&
			sub_name, const adobe::value_t& sub_value,
			binder_list_t& binder_list,
		        const adobe::eve_t::signal_suite_t::eve_place_proc_t& placer = 0 ) {
			//
			// Make our substituted list of parameters.
			//
			adobe::dictionary_t params( parameters );
			//
			// Iterate through all of the parameters. If
			// we encounter the name "sub_name" anywhere
			// then we substitute it.
			//
			adobe::dictionary_t::iterator first_p	= params.begin();
			adobe::dictionary_t::iterator last_p	= params.end();
			while( (first_p != last_p) && sub_name ) {
				adobe::name_t out_name;
				first_p->second.get( out_name );
				if( out_name == sub_name ) {
					params.set( first_p->first, sub_value );
				}
				first_p++;
			}
			//
			// Binders could be in a parameter of any name. Walk through
			// all of the parameters and check for binders.
			//
			first_p = params.begin();
			last_p = params.end();
			while( (first_p != last_p) && sub_name ) {
				adobe::binder_ptr_t binder;
				first_p->second.get( binder );
			    if( binder ) {
					binder = binder->copy();
					if( !binder ) throw std::runtime_error( "binder "
						"failed to copy!" );
					binder->substitute( sub_name, sub_value );
					params.set( first_p->first, adobe::value_t( binder ) );
					binder_list.push_back( binder );
				}
				first_p++;
			}
			//
			// Attempt to build ourselves, then all of our children.
			//
			if( name == adobe::static_name_t( "generator_root" ) ) {
				adobe::widget_node_t us = build_root( token, parent, placer ); 
				build_children( token, us, f, sub_name, sub_value, binder_list );
				return us;
			}
			//
			// Build a simple container that will inform the generator
			// of the bounds that this child is assigned.
			//
			adobe::widget_node_t root( parent );
			if( placer ) root = build_root( token, parent, placer );
			adobe::widget_node_t us = f.build( name, params, root, token );
			build_children( token, us, f, sub_name, sub_value, binder_list );
			//
			// Return ourselves. This is only used for the root item.
			//
			return us;
		}
	};
	//
	/// This factory function builds a list of records. We abuse the display_token_m
	/// to contain the parent record (!).
	///
	/// \param	name	the name of the view to record.
	/// \param	params	the parameters to create the view record with.
	/// \param	parent	the parent widget node.
	/// \param	token	the factory token (forgotten, unused).
	/// \return	a bad widget_node which has the record* stored in the display_token.
	//
	adobe::widget_node_t make_record( adobe::name_t name,
		const adobe::dictionary_t& params, const adobe::widget_node_t& parent,
		const adobe::factory_token_t& token ) {
		//
		// Record this item, and return it as a parent.
		//
		return adobe::widget_node_t( parent.size_m, parent.eve_token_m,
			new record( parent.display_token_m, name, params ),
			parent.overlay_token_m );
	}
	//
	/// An item is a created view. This structure is used by the generator
	/// class to keep track of the items it has created, and if they are currently
	/// in use.
	//
	struct item_t {
		//
		// See: http://thedailywtf.com/forums/74943/postattachment.aspx
		//
		struct widget_node_container_t {
			adobe::widget_node_t n;
			widget_node_container_t( const adobe::widget_node_t& node ) : n( node ) {}
		};
		
		item_t( adobe::assemblage_t* assemble )
			: widget_node( 0 ), assemblage( assemble ), view_proxy( 0 ),
			  is_stub( true ), make_real( false ), in_use( false ) {}
		~item_t() {
			if( assemblage ) delete assemblage;
			if( view_proxy ) adobe::eve_t::delete_proxy_tree( view_proxy );
			if( widget_node ) delete widget_node;
		}
		void set_widget_node( const adobe::widget_node_t& node ) {
			if( widget_node ) delete widget_node;
			widget_node = new widget_node_container_t( node );
		}
		void remove( adobe::eve_t* layout ) {
			if( !layout || !widget_node || view_proxy ) return;
			view_proxy = layout->remove_view_element( widget_node->n.eve_token_m );
		}

		void insert( adobe::eve_t* layout, adobe::eve_t::iterator parent ) {
			if( !layout || !view_proxy || !widget_node ) return;
			widget_node->n.eve_token_m = layout->insert_view_element( parent, view_proxy );
			adobe::eve_t::delete_proxy_tree( view_proxy );
			view_proxy = 0;
		}

		widget_node_container_t*	widget_node;
		adobe::assemblage_t*		assemblage;
		adobe::eve_t::proxy_tree_t*	view_proxy;
		bool				is_stub;
		bool				make_real;
		bool				in_use;
		adobe::eve_t::place_data_t	place_data;
		adobe::value_t			value;
		record::binder_list_t		binder_list;
	};
	//
	// Now what do we need...
	//
	//  * new record( "root of generator" ... )
	//  * push factory( make_record )
	//  * new generator
	//   * binds to range
	//   * creates widgets
	//   * calls evalutate
	//  * add generator to list of things to get deleted.
	//  * return parent (with "root of generator" record) as widget node.
	//
	/// The generator class owns a tree of records, and is bound to a range. When
	/// the range changes it generates/shuffles the record tree for each item in
	/// the range, typically substituting the item into the parameters of the views
	/// that are generated.
	///
	/// The virtual bounding box feature allows the generator to bind to a cell which
	/// contains the visible bounding box inside the generator. This means that the
	/// generator can opt to not create certain items if they are outside of the box.
	//
	class generator {
		typedef std::vector<item_t*>		item_list_t;
		typedef std::map<unsigned int, item_t*> item_map_t;
		typedef std::deque<item_t*>		item_stack_t;
		record*			_record;	///< Record to build items from.
		adobe::widget_node_t	_us;		///< Our widget node.
		factory::factory_t	_factory;	///< The factory to create children with.
		adobe::binder_helper_t	_binder;	///< Used to bind us to a model.
		eve_client::button_notifier_t	_notifier;	///< For children to call on.
		adobe::name_t		_subst;		///< The name to substitute in.
		rectangle		_bbox;		///< Virtual bounding box (if one exists).
		rectangle		_originalBbox;	///< Original bounding box (not grown).
		bool			_virtual;	///< Are we in virtual list mode?
		long			_childWidth;	///< Width of the child (for virtual mode).
		long			_childHeight;	///< Height of the child (for virtual mode).
		util::concept::List		_valueList;	///< Current set of values we're bound to.
		boost::signals::scoped_connection	_onShow;	///< Used to initialize.
		adobe::value_t		_sourcePump;	///< The source datapump to initialize _binder with.
		bool			_initialized;	///< Have we been initialized or not yet?
		bool			_measured;	///< Have we measured our child or not yet?
		item_list_t		_stubs;		///< The stubs we use for layout and offset.
		item_map_t		_real_items;	///< Real items we have created.
		item_stack_t		_free_real_items;	///< Real items that aren't in use.
		bool			_window_dirty;	///< Used when building child tokens.
		//
		// void _ensure_stubs()
		//
		/// Ensure that we have enough stubs. We need as many stubs as we have values
		/// to make views for.
		//
		void _ensure_stubs() {
			if( _stubs.size() >= _valueList.size() ) return;
			adobe::value_t v;
			adobe::name_t n;
			while( _stubs.size() < _valueList.size() ) {
				_stubs.push_back( _create_item( v, n, false ) );
			}
		}
		//
		// void _place_child( const cdata, const pdata )
		// 
		/// This function is called when a child item is placed. It lets us know what
		/// size the child item is so that we can determine the child dimensions for
		/// virtual box behavior. We don't need to do anything else, as this is typically
		/// attached to a row container (which has no place signal).
		///
		/// \param	item	the item to which this value belongs.
		/// \param	cdata	calculated data.
		/// \param	pdata	placement data.
		//
		void _place_child( item_t* item,
			const adobe::eve_t::calculate_data_t& cdata,
			const adobe::eve_t::place_data_t& pdata ) {
			item->place_data = pdata;
		}
		//
		// void _measure()
		//
		/// This function will measure the size of one child, and set
		/// _childWidth and _childHeight appropriately. It should only
		/// be called before any items have been created and it is only
		/// required for virtual mode.
		///
		/// \param	sample_subst	a sample substitution value to use.
		//
		void _measure( const adobe::value_t& sample_subst ) {
			if( _measured ) return;
			item_t* measure = _create_item( sample_subst, _subst, true );
			//
			// Evaluate to get the real dimensions.
			//
			_factory.token.layout_m->evaluate( adobe::eve_t::evaluate_nested );
			//
			// Take the width and height from this measurement
			// item.
			//
			if( measure ) {
				_childWidth = measure->place_data.horizontal().length_m;
				_childHeight = measure->place_data.vertical().length_m;
				//
				// Now remove this item from the layout.
				//
				measure->remove( _factory.token.layout_m );
				delete measure;
			}
			_measured = true;
		}
		//
		// void _promote_bounds()
		//
		/// This function will mark-promote all items that lie inside the virtual
		/// box to real items, and will mark-demote all other items to stubs. Note
		/// that this function doesn't actually insert or remove any items, it just
		/// marks them for insertion or removal by _xfrom_all.
		//
		void _promote_bounds() {
			for( item_list_t::iterator i = _stubs.begin(); i != _stubs.end(); i++ ) {
				//
				// Force everything to be real when not in virtual mode.
				//
				if( !_virtual ) {
					(*i)->make_real = true;
					continue;
				}
				(*i)->make_real = contains( _bbox, (*i)->place_data );
			}
		}
		//
		// item_t* _create_item( const adobe::value_t& item, const adobe::name_t& sub_name )
		//
		/// Create a new item using the given item value and substitution name.
		///
		/// \param	item		the value that parameterizes this item.
		/// \param	sub_name	the name to substitute the URL into.
		/// \param	real_item	make a real item or make a stub.
		/// \return	the new item.
		//
		item_t* _create_item( const adobe::value_t& item, const adobe::name_t& sub_name, bool real_item ) {
			factory f;
			factory_token_ptr_t child_token;
			adobe::assemblage_t* assemblage( new adobe::assemblage_t() );
			
			child_token.assemblage_m = assemblage;
			try {
				bool* window_dirty = new bool;// &_window_dirty;
				adobe::ui_overlay_t fake_overlay;
				eve_client::serialize_signal_t	fake_stream;
				eve_client::show_window_signal_t fake_show;
				*window_dirty = true;
				assemblage->delete_on_destruction( window_dirty );
				//
				// XXX: This adobe_token stuff is wrong!
				// XXX: We need to store the display, etc, when
				// XXX: this generator gets created.
				//
				adobe::factory_token_t adobe_token(
					adobe::get_main_display(),
					*assemblage,
					*_factory.token.layout_m,
					*_factory.token.sheet_m,
					_notifier, // notifier
					fake_stream, // widget stream
					fake_show, // show window
					fake_overlay, // overlay
					*window_dirty // window dirty
					);
				//
				// Build a stub or real widget.
				//
				item_t* new_item = 0;
				if( real_item ) {
					new_item = new item_t( assemblage );
					new_item->set_widget_node(
						_record->build( adobe_token, _us, f,
							sub_name, item,
							new_item->binder_list,
							boost::bind(
								&generator::_place_child,
								this,
								new_item,
								_1, _2 )
							) );
					new_item->value = item;
					new_item->is_stub = false;
					new_item->in_use = true;
				} else {
					new_item = new item_t( assemblage );
					new_item->set_widget_node(
						_record->build_root( adobe_token, _us,
							boost::bind(
								&generator::_place_child,
								this,
								new_item,
								_1, _2 ),
							_childWidth, _childHeight, true ) );
					new_item->is_stub = true;
					new_item->in_use = true;
				}
				return new_item;
			} catch( ... ) {
				delete assemblage;
				throw;
			}
		}
		//
		// void _update( const adobe::value_t& val )
		//
		/// Update the list of items that we need views for.
		///
		/// \param	val	the new list of items.
		//
		void _update( const adobe::value_t& val ) {
			if( !_record ) return;
			//
			// Try to get the list of URLs we will create the child views with.
			//
			util::concept::List values = util::concept::get_list(val);
			_valueList = values;
			//
			// Remove all of our current items from our view, and mark them all
			// for destruction.
			//
			for( item_map_t::iterator i = _real_items.begin(); i != _real_items.end(); i++ ) {
				i->second->remove( _factory.token.layout_m );
				i->second->in_use = false;
			}
			if( _virtual ) {
				//
				// If we haven't measured and we're in virtual mode and have some
				// values then measure ourselves.
				//
				if( !_measured && !_valueList.empty() ) _measure( _valueList.at(0) );
				//
				// Ensure that we have enough stubs to cover this.
				//
				_ensure_stubs();
				//
				// Remove all of the stubs.
				//
				for( item_list_t::iterator i = _stubs.begin(); i != _stubs.end(); i++ ) {
					(*i)->remove( _factory.token.layout_m );
					(*i)->make_real = false;
				}
				//
				// Now that we have all the stubs, we can insert them into the
				// layout. We will then be able to get all of the correct
				// geometries. If we are not in virtual mode, then we don't
				// insert more stubs than we have items.
				//
				for( item_list_t::reverse_iterator i = _stubs.rbegin(); i != _stubs.rend(); i++ )
					(*i)->insert( _factory.token.layout_m, _us.eve_token_m );
				//
				// Force the Eve layout to update.
				//
				_factory.token.layout_m->evaluate( adobe::eve_t::evaluate_nested );
				//
				// Now promote any children that are visible.
				//
				_promote_bounds();
			}
			//
			// Now that we know what the bounds are, and the
			// indices of the real items, we can sort out the
			// order of the _real_items. Only bothering to
			// look at the items that we know to be real makes
			// this operation O(m**2) where m is the number
			// of real items. Note that typically 0 < m < 50,
			// whereas 0 < n < 10000, so this is quite some
			// saving compared to an O(m*n) or O(n**2)
			// implementation (where n is the total number of
			// values).
			//
			item_map_t correct_real_items;
			for( unsigned int i = 0; i < _valueList.size(); i++ ) {
				item_t* stub(0);
				if( _virtual ) {
					stub = _stubs[i];
					if( !stub || !stub->make_real ) continue;
				}
				//
				// Ok, this one is real.
				//
				adobe::value_t val( _valueList.at( i ) );
				//
				// Search for it in _real_items. First we
				// check at this index in case it hasn't
				// changed between calls to _update.
				//
				item_map_t::iterator ri = _real_items.find( i );
				if( (ri != _real_items.end()) && (ri->second->value == val) ) {
					ri->second->in_use = true;
					correct_real_items[i] = ri->second;
					if( _virtual ) ri->second->place_data = stub->place_data;
					continue;
				}
				//
				// It wasn't at the same index. Now we need
				// to go through all of _real_items (ignoring
				// items that are now in_use) looking for
				// one with the right value.
				//
				for( ri = _real_items.begin(); ri != _real_items.end(); ri++ ) {
					if( ri->second->in_use ) continue;
					if( ri->second->value == val ) {
						ri->second->in_use = true;
						correct_real_items[i] = ri->second;
						if( _virtual ) ri->second->place_data = stub->place_data;
						break;
					}
				}
				//
				// We just don't have that item already
				// created. _xform_all will have to create
				// it for us.
				//
			}
			//
			// Before assigning the correct_real_items to
			// _real_items we need to go and delete all of
			// the items we're not using any more.
			//
			for( item_map_t::iterator i = _real_items.begin(); i != _real_items.end(); i++ ) {
				if( !i->second->in_use ) delete i->second;
			}
			_real_items = correct_real_items;
			//
			// When in virtual mode transform all of the stubs
			// into real items.
			//
			if( _virtual )
				_xform_all_new( true );
			else {
				//
				// Not in virtual mode. We have to build all
				// of the real items or use existing ones.
				//
				item_list_t ordered_items;
				for( unsigned int i = 0; i < _valueList.size(); i++ ) {
					//
					// If this item already exists then use the existant one,
					// otherwise create a new one.
					//
					item_map_t::iterator ri( _real_items.find( i ) );
					if( ri != _real_items.end() ) {
						//
						// It exists, use it.
						//
						ri->second->in_use = true;
						ordered_items.push_back( ri->second );
					} else {
						//
						// Have to create a new one.
						//
						item_t* real = _create_item( _valueList.at(i), _subst, true );
						real->remove( _factory.token.layout_m );
						ordered_items.push_back( real );
						_real_items[i] = real;
					}
				}
				//
				// Now reinsert all of the correctly ordered real_items.
				//
				std::for_each( ordered_items.rbegin(), ordered_items.rend(),
					boost::bind( &item_t::insert, _1, _factory.token.layout_m, _us.eve_token_m ) );
				_factory.token.layout_m->evaluate( adobe::eve_t::evaluate_nested );
			}
			//
			// Force the sheet to deliver new values. This is required because
			// the widgets that we just created won't have values yet (and
			// because the sheet is already around, won't get the initial
			// value message).
			//
			_factory.token.sheet_m->update();
		}
		void _xform_all_new( bool changes = false ) {
			//
			// 1. Remove everything from layout.
			// 2. Find the real items that aren't in use, add them to a list.
			// 2.a. Reinsert those stubs that aren't make_real.
			//   b. Insert real items for those stubs that are make_real,
			//      reusing real items if possible.
			//   c. Delete real items that aren't in use any more.
			//
			item_stack_t unused_real_items( _free_real_items );
			item_map_t used_real_items;
			for( item_map_t::iterator i = _real_items.begin(); i != _real_items.end(); i++ ) {
				i->second->in_use = false;
				i->second->remove( _factory.token.layout_m );
				if( !_stubs[i->first]->make_real )
					unused_real_items.push_back( i->second );
				else used_real_items[i->first] = i->second;
			}
			_real_items = used_real_items;
			_free_real_items = unused_real_items;
			item_list_t ordered_items;
			//
			// Iterate through by index, as we use the index to look up
			// values.
			//
			unsigned int ct = std::min( _stubs.size(), _valueList.size() );
			for( unsigned int i = 0; i < ct; i++ ) {
				item_t* stub( _stubs[i] );
				stub->remove( _factory.token.layout_m );
				//
				// Force the first and last elements into always being real.
				//
				bool is_first_or_last( (i == 0) || (i == _valueList.size() - 1) );
				if( is_first_or_last ) stub->make_real = true;
				//
				// Either put a real one in, or put the stub back in.
				//
				if( stub->make_real || !_virtual ) {
					//
					// We use an integer index into the set of real items
					// as integer comparisons are always faster than value
					// comparisons (not least because values have no natural
					// order defined, so most search algorithms don't apply).
					//
					adobe::value_t key( _valueList.at( i ) );
					item_map_t::iterator ri( _real_items.find( i ) );
					if( ri != _real_items.end() ) {
						//
						// Great, this item already exists. Let's use it.
						//
						ri->second->in_use = true;
						ordered_items.push_back( ri->second );
					} else {
						//
						// This index hasn't had a real item created
						// for it.
						//
						// 1. Check to see if we have a free already
						//    existing real item that we can change
						//    to match this item.
						// 2. If not, create a new real item.
						//
						item_t* real( 0 );
						if( !_free_real_items.empty() && RISKY_SUBSTITUTE_OPT ) {
							real = _free_real_items.front();
							_free_real_items.pop_front();
							adobe::for_each( real->binder_list, boost::bind( &adobe::binder_t::substitute, _1, _subst, key ) );
						} else {
							real = _create_item( key, _subst, true );
							real->remove( _factory.token.layout_m );
						}
						_real_items[i] = real;
						ordered_items.push_back( real );
						changes = true;
					}
				} else {
					ordered_items.push_back( stub );
				}
			}
			//
			// Now, reinsert all of the items.
			//
			std::for_each( ordered_items.rbegin(), ordered_items.rend(),
				boost::bind( &item_t::insert, _1, _factory.token.layout_m, _us.eve_token_m ) );
			//
			// Erase any real items that are no longer in use. If there are
			// any items here, then we need to relayout.
			//
			while( _free_real_items.size() > MAX_EXCESS_REAL_ITEMS ) {
				delete _free_real_items.front();
				_free_real_items.pop_front();
			}
			if( changes ) _factory.token.layout_m->evaluate( adobe::eve_t::evaluate_nested );
		}
		void _updateBoundingBox( const adobe::value_t& box ) {
			//
			// If we got here then somebody already did a layout of our
			// views. We needn't perform another, but we do need to copy
			// the bounds from the real views into the stubs so that
			// promote_bounds (which operates on stubs) has the correct
			// positions.
			//
			// Make sure we don't keep getting called from _update when in
			// virtual mode.
			//
			rectangle this_box;
			if( !box.get( this_box ) ) return;
			//
			// Ignore negative sized boxes, they are an artifact of initial
			// placement.
			//
			if( this_box.w < 0 || this_box.h < 0 ) return;
			//
			// If this_box goes outside of _bbox, or if it has different
			// *dimensions* to the _originalBbox then we need to rebuild
			// _bbox.
			//
			static int count = 0;
			count++;
			if( (this_box.w != _originalBbox.w || this_box.h != _originalBbox.h) ||
			    (this_box.x < _bbox.x) || (this_box.y < _bbox.y) ||
			    (this_box.x + this_box.w > _bbox.x + _bbox.w) ||
			    (this_box.y + this_box.h > _bbox.y + _bbox.h) ) {
				//
				// We need to recalculate the box and possibly regenerate
				// some of the children.
				//
				_originalBbox = this_box;
				_bbox.w = this_box.w * 2;
				_bbox.h = this_box.h * 2;
				_bbox.x = this_box.x - (this_box.w / 2);
				_bbox.y = this_box.y - (this_box.h / 2);
			} else return;
			//
			// Copy the real bounds over to the stubs.
			//
			for( item_map_t::iterator i = _real_items.begin(); i != _real_items.end(); i++ ) {
				_stubs[i->first]->place_data = i->second->place_data;
			}
			//
			// Now that we have new bounds, promote/demote all of our children.
			// We have to do an evaluation here just to make sure that everything
			// is in it's right place for promotion/demotion.
			//
			_promote_bounds();
			_xform_all_new();
		}
		void _initialize() {
			if( _initialized ) return;
			_binder.initialize( _sourcePump, boost::bind( &generator::_update, this, _1 ), 0 );
			_initialized = true;
		}
	  public:
		generator( const adobe::dictionary_t&	params,
			const adobe::factory_token_t&	token,
			const adobe::widget_node_t&	us,
			factory& f )
		 : _record( 0 ), _us( us ), _factory( f.top( token ) ),
		   _binder( token.sheet_m ), _notifier( token.notifier_m ),
		   _virtual( false ), _initialized( false ), _measured( false ) {
			//
			// Get the things we need to work (bind, iterator).
			//
			_sourcePump = params.at( adobe::static_name_t( "bind" ) );
			params.get( adobe::static_name_t( "iterator" ), _subst );
			//
			// Create a row as the root record. This is a container that we can
			// create and doesn't mess anything up.
			//
			_record = new record( 0, adobe::static_name_t( "generator_root" ), adobe::dictionary_t() );
			//
			// Make children use our special factory that makes records instead
			// of actual widgets. Note that the way we saved the factory_t
			// means that embedding generators in generators doesn't work (!).
			// The alternative (only using the token and default factory
			// function) might be okay.
			//
			f.push( factory::factory_t( factory_token_ptr_t(),
				make_record ) );
			//
			// Initialize ourselves once the window has been shown. This means
			// we don't try to create things before the factory has recorded
			// all of our children.
			//
			boost::function<void ()> onShowFunction( boost::bind( &generator::_initialize, this ) );
			_onShow = token.show_window_signal_m.connect( onShowFunction );
			//
			// If we have a name for the virtual bounding box then we can bind
			// to that cell. We always bind directly to the sheet, because the
			// virtual_box is only ever in the sheet.
			//
			if( params.count( adobe::static_name_t( "virtual_box" ) ) ) {
				adobe::name_t bbox_name;
				params.get( adobe::static_name_t( "virtual_box" ), bbox_name );
				token.assemblage_m.hold_connection(
					token.sheet_m.monitor_value( bbox_name,
						boost::bind( &generator::_updateBoundingBox, this,
							_1 ) ) );
				_virtual = true;
			}
		}
		virtual ~generator() {
			delete _record;
			item_map_t::iterator first( _real_items.begin() );
			item_map_t::iterator last( _real_items.end() );
			for( item_map_t::iterator i = first; i != last; i++ )
				delete i->second;
			for( item_stack_t::iterator i = _free_real_items.begin(); i != _free_real_items.end(); i++ )
				delete *i;
			for( item_list_t::iterator i = _stubs.begin(); i != _stubs.end(); i++ )
				delete *i;
		}
		adobe::widget_node_t node() const {
			return adobe::widget_node_t( _us.size_m, _us.eve_token_m,
				_record, _us.overlay_token_m );
		}
	};

	adobe::widget_node_t generator_factory( const adobe::dictionary_t& parameters,
		const adobe::widget_node_t& parent,
		const adobe::factory_token_t& token,
		factory* f ) {
		//
		// Create our generator, and register it to be destroyed with everything
		// else.
		//
		generator* g( new generator( parameters, token, parent, *f ) );
		token.assemblage_m.delete_on_destruction( g );
		return g->node();
	}
};

